A penetration test is a set of risk assessment methodologies where the “penetration testers” or auditors assume the standpoint of an attacker in order to examine security controls in place of an infrastructure of networked computers and applications. Typically, the penetration tester will mimic a specific profile of an attacker, which can be a disgruntled employee in a given area of an organization, an external “script kiddie” or a corporate spy. The result of the penetration test is generally a report that includes the list of threats that this profile of an attacker could exercise. For example, a disgruntled employee in accounting may be able to steal the clients and credit card database, a corporate spy may be able to access secret Intellectual Property, and a “script kiddie” may compromise and leave unavailable the machines for all the cashiers of a retailer business.
The last ten (10) years have witnessed the development of a new kind of information security tool: the Penetration Testing Framework. An exemplary description of a Penetration Testing Framework is provided by U.S. Pat. No. 7,757,293, entitled, “Automated Computer System Security Compromise,” by Caceres et al., filed on Jan. 22, 2002, which is incorporated by preference in its entirety. Penetration Testing Frameworks facilitate the work of penetration testers on networked computers and applications, and make the security assessment more accessible to non-experts. The main difference between these tools and network security scanners is that Penetration Testing Frameworks have the ability to exploit vulnerabilities, and help to expose risk by assessing the complete attack path an attacker would take, whereas scanners simply look for evidence of vulnerabilities.
Penetration tests involve successive steps of information gathering and vulnerability exploitation. In an information-gathering step the penetration-testing framework helps the user to gather information about the networked computers and applications under attack (available hosts, their operating systems, open ports, and the services running in them). In a vulnerability-exploitation step the user actively tries to leverage vulnerabilities present on specific assets in the network and gain unwarranted access to these assets. When this leverage is through an exploit executed against a vulnerable host (e.g., a desktop, laptop or server computer system) and this exploit is successful, the host becomes compromised and can be used to perform further information gathering, or the machine can be used to execute subsequent attack steps. This shift in the source of the actions of an attacker is called pivoting. Newly compromised machines or applications can serve as the source for posterior information gathering. This new information might reveal previously unknown vulnerabilities. As a result, the phases of information gathering and exploiting usually succeed one another.
Other forms of leveraging vulnerabilities are, for example but not limited to, exploitation of application vulnerabilities and gaining non-authorized access to Wi-Fi communication channels or other types of assets.
As attackers have evolved, so have penetration-testing frameworks: they have become more complex, covering new attack vectors, shipping increasing numbers of exploits (hereafter exploit modules) and information gathering modules. With this evolution, the problem of successfully mimicking an attacker has become a complex task.
The penetration tester is a skilled technician who can develop exploit modules, understands the consequences of using one exploit module over another one in a particular situation, or how to replace the exploit module in case it does not work, and can craft an attack towards a given objective in accordance with constraints underlying the scenario at hand. Understanding the consequences of executing each attack action is fundamental for an effective penetration test. While different actions may have the same outcome (when successful), they will typically last differently, have different probabilities of success, take different requirements, and have other effects.
During the exercise of a penetration test, the penetration tester will execute penetration-testing modules (information-gathering or exploit modules), and by executing the modules he may obtain new assets. An example is the penetration tester running an exploit module from his local agent against a remote target host, and when the exploit module succeeds the module installs a remote agent in the remote target host. This remote agent is an asset that is added to assets of the penetration tester. During his work, the penetration tester will attempt to achieve certain objectives. One example of such an objective may be installing a remote agent in a web server, or obtaining a credit card database. These special objectives are referred to as the goal of the penetration test. Typically, the penetration tester will plan a penetration test looking to obtain certain specific goals.
Hence, if a penetration tester has some partial knowledge of a network he is auditing, he can define the potential actions that he may follow and from those derive the new states in which the network would be, and move on to define new actions and new states until he reaches a state that is worth reporting; in particular, if one of the goals is reached. However, the number of possibilities that are available to the penetration tester, and hence the number of nodes and edges that constitute an attack graph, may be large. Explicitly the number of nodes and edges that constitute an attack graph may be comparable to the number of computers in the network to the power of the number of available attack modules, so that it may turn to be an infeasible problem to visualize them, or pick one of these attacks out from the lot that has a special property, such as, for example, being the quickest.
In computer science a problem is said to be infeasible when despite the algorithm used to solve it, the amount of resources needed (computational power or storage) is extremely large and the combinations to be tested quickly increases with the size of the problem.
Computer attacks, including those executed with aid of a penetration-testing framework, are the object of study of computer scientists and computer security professionals. In particular, the threats or potential attacks underlying a target network can be described through attack graphs. In particular, attack graphs can be used to model an attack before executing the attack, or during execution of an attack in order to analyze next steps.
There are many ways to model an attack through attack graphs. To define one such model, one needs to define “nodes” and “edges.” In one possible way to model attack graphs, nodes identify a state of the attack, while edges represent individual actions that the attacker may follow during the attack. Generally speaking, the state is defined by the knowledge that the attacker has gained about the network, and the changes he has inserted in the network, from the start of the attack until the action (edge) preceding this node. The new assets obtained by the attacker are different depending on whether the assets were obtained after an action is run or before an action is run. In attack graphs, an attack path is a path in the graph from a start node to the goal node; that is, a sequence of actions, where the preconditions for an action are always guaranteed by the previous actions and the last action conquers the goal.
However, selecting one such attack path is not an easy task. Many attack paths may be possible, each one underlying different combinations of attacks and parameters. For example, one of the attacks suggested by the attack path may turn out to be faster, another one may have better chances of succeeding, and another one may cause alerts in the control or security monitoring systems of the target network. In fact, penetration-testing frameworks do not include the information summarizing how much time each of its penetration-testing modules takes to run, their probability of success, and other factors. Moreover, even if this information were available, the problem of piecing the information together to weigh attack paths and deciding whether one is better-suited than another one in a particular case, seems to be outside of reach of the standard penetration tester.
Previous attack graph models do not include a concise way of summarizing the different alternatives the attacker may choose from to conduct an attack and the parameters (expected time, probability of success, etc.) underlying these attack paths, thus allowing an explosion of combinations, deterministically intractable for medium-sized networks and larger networks. In particular, previous attach graph models do not tackle the problem of picking an attack path that minimizes the expected time to be run, or which is expected to raise a lower number of alerts (logs) in the control systems, or has a bigger probability of success.
Another drawback of previous attack planning systems is that they are deterministic, in the sense that they output the best solution (or in any case, the best few solutions). Being that penetration tests are intrinsically probabilistic (e.g., one cannot predict the outcome of each penetration testing module with absolute certainty), deterministic attack plans are not suited for assisting the penetration tester. As an example, if a step in the deterministic attack plan fails, while the plan is being executed, the penetration tester must drop this attack plan and replace it with another one.
Thus, a heretofore unaddressed need exists in the industry to address the aforementioned deficiencies and inadequacies.